ABC

Limit pamięci: 64 MB

Dane są dwa ciągi znaków i , składające się z liter 'a','b' i 'c'. Należy znaleźć najdłuższy niemalejący wspólny podciąg ciągów i . Inaczej mówiąc, należy znaleźć najdłuższy ciąg, który:

• jest podciągiem ciągów i , czyli da się go otrzymać przez usunięcie pewnych liter z ciągów i ;
• jest niemalejący pod względem kolejności liter w alfabecie, czyli przed wystąpieniem litery nie wystąpi litera o większym kodzie ASCII niż .

Wejście

W pierwszej linii znajdują się dwie liczby całkowite i (), oznaczające długości ciągów i . W drugiej linii znajduje się ciąg , a w następnej .

Wyjście

W pierwszym wierszu należy wypisać długość najdłuższego ciągu spełniającego warunki zadania.

Przykład

Dla danych wejściowych:

5 6
cabbc
bacbcc

poprawną odpowiedzią jest:

3

Autor zadania: Łukasz Jocz (zapożyczenie).